package com.hdu.point_offer;

public class lcr170 {
        class Solution {
            public int reversePairs(int[] record) {
                return merge(record, 0, record.length - 1);
            }

            int merge(int[] records, int l, int r)
            {
                if (l >= r)
                {
                    return 0;
                }
                int mid = l + (r - l) / 2;
                int ans = merge(records, l, mid) + merge(records, mid + 1, r);
                ans += doMerge(records, l, mid, mid + 1, r);
                return ans;
            }

            int doMerge(int[] records, int l1, int r1, int l2, int r2)
            {
                int len = r2 - l1 + 1;
                int[] tmp = new int[len];
                int cur1 = l1;
                int cur2 = l2;
                int index = 0;
                int ans = 0;
                while (cur1 <= r1 && cur2 <= r2)
                {
                    if (records[cur1] <= records[cur2])
                    {
                        tmp[index++] = records[cur1++];
                    }
                    else {
                        tmp[index++] = records[cur2++];
                        ans += r2 - cur1;
                    }
                }
                while (cur1 <= r1)
                {
                    tmp[index++] = records[cur1++];
                }
                while (cur2 <= r2)
                {
                    tmp[index++] = records[cur2++];
                }
                index = 0;
                for (int i = l1; i <= r2; i++)
                {
                    records[i] = tmp[index++];
                }
                return ans;
            }
        }
}
